#include "Student.h"

Student::Student(){
  std_no=0;
  major=0;
  GPA=-1;
}
 
Student::Student(int std_nodata,char majordata, double GPAdata){
  std_no=std_nodata;
  major=majordata;
  GPA=GPAdata;
}

char Student::get_major(){
  return major;
}
 
double Student::get_GPA(){
  return GPA;
}

int Student::printout(){
  std::cout << std_no << "," << major << "," << GPA << std::endl;
  return 0;
}

Heap::Heap(){
  data=NULL;
  length=0;
}
  
Heap::Heap(Student *heapdata, int l){
  data = new Student[l];
  for (int i=0; i<l ; i++)
    data[i]=heapdata[i];
  length=l;
  for (int i=PARENT(l-1); i>=0 ; i--)
    shiftdown(i);
}
  
Heap::~Heap(){
  delete[] data;
}
  
int Heap::get_length(){
  return length;
}
  
int Heap::shiftdown(int i){
  int lc=LEFTCHILD(i);
  int rc=RIGHTCHILD(i);
  int child = -1;
  if (lc >= length)
    return 0;
  if (data[lc].get_major() >= data[rc].get_major())
    child = lc;
  if (data[rc].get_major() > data[lc].get_major() && rc < length)
    child = rc;
  if (data[child].get_major() > data[i].get_major() && child != -1){
    Student tmp = data[i];
    data[i] = data[child];
    data[child] = tmp;
    shiftdown(child);
  }
  else
    return 0;
}
  
int Heap::heapsort(){
  int l = length;
  while(length > 0){
    Student tmp = data[0];
    data[0] = data[length - 1];
    data[length - 1] = tmp;
    length--;
    shiftdown(0);
  }
  length = l;
  return 0;
}

int Heap::write_Student(Student *A){
  for (int i=0; i< length ; i++)
    A[i]=data[i];
  return 0;
}

int sort_m(Student *A,int n){
  Heap H(A,n);
  H.heapsort();
  H.write_Student(A);
  return 0;
}

int arrange(Student *A,int n){
  int i = 1;
  int t = 0;
  while ( i < n ){
    if (A[i].get_major() != A[i-1].get_major()){
      MergeSort(A,t,i-1);
      t=i;
    }
    i++;
  }
  MergeSort(A,t,i-1);
  return 0;
}

int Merge(Student *A, int p, int q, int r){
  int n1 = r - p + 1;
  int n2 = q - r;
  Student *L = new Student[n1+1];
  Student *R = new Student[n2+1];
  for (int i = 0; i < n1 ; i++)
    L[i] = A[p + i];
  for (int i = 0; i < n2 ; i++)
    R[i] = A[r + 1 + i];
  L[n1] = Student(0,0,-1);
  R[n2] = Student(0,0,-1);
  int i=0;
  int j=0;
  for (int k = p; k < q + 1 ; k++){
    if (L[i].get_GPA() >= R[j].get_GPA()){
      A[k] = L[i];
      i++;
    }
    else{
      A[k] = R[j];
      j++;
    }
  }
  delete[] L;
  delete[] R;
  return 0;
}

int MergeSort(Student *A, int p, int q){
  int r;
  if (p < q){
    r = (p + q)/2;
    MergeSort(A,p,r);
    MergeSort(A,r+1,q);
    Merge(A,p,q,r);
  }
  return 0;
}
